/***************************************************************************
 *            routines.c
 *
 *  Tue Aug 30 17:36:32 2005
 *  Copyright  2005  Yitzhak Grossman
 *  celejar@gmail.com
 ****************************************************************************/

/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
 

/* routines for sudoku generator - originally written for sudoku solver,
 * borrowed (modified) for generator
 */
 

#include <stdio.h>
#include <stdlib.h>
#define WII
#ifndef WII
#include "../include/sudoku.h"
#else
#include "sudoku.h"
#endif

#define DEBUG2

int set_cell(struct sudoku_info *sudoku, int i, int j, int value)
{
	int k, l;
	if (sudoku->info[i][j][value - 1] == NO) return 1;
	//~ if (sudoku->grid[i][j]) test();
	sudoku->grid[i][j] = value;
	if (++(sudoku->known) == 81) 
	{
		Solutions++;
		sudoku->grid[i][j] = 0;
		--(sudoku->known);
		return 1;
	}
	//~ printf("Setting cell %d,%d to %d\n", i, j, value);
	sudoku->info[i][j][value - 1] = YES;
	for (k = 0; k < 9; k++)
	{
		if (k != value - 1) sudoku->info[i][j][k] = NO;
		if (k != j) sudoku->info[i][k][value - 1] = NO;
		if (k != i) sudoku->info[k][j][value - 1] = NO;
	}
	for (k = (i - (i % 3)); k < i - (i % 3) + 3; k++)
		for (l = (j - (j % 3)); l < j - (j % 3) + 3; l++)
			if (k != i || l != j) sudoku->info[k][l][value - 1] = NO;
	return 0;
}
int add_cells(struct sudoku_info *sudoku)
{
	int flag, val;
	do
	{
		flag = 0;
		if ((val = find_cells(sudoku)) == 1) return 1;
		flag |= val;
		if ((val = find_rows(sudoku)) == 1) return 1;
		flag |= val;
		if ((val = find_columns(sudoku)) == 1) return 1;
		flag |= val;
		if ((val = find_grids(sudoku)) == 1) return 1;
		flag |= val;
	} 
	while (flag);
	return 0;
}
int find_cells(struct sudoku_info *sudoku)
{
	int i, j, k, counter, flag = 0;
	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
		{
			if (sudoku->grid[i][j]) continue;
			for (k = 0, counter = 0; k < 9; k++)
				if (sudoku->info[i][j][k] == NO) counter++;
			if (counter < 8) continue;
			if (counter > 8) return 1;
			for (k = 0; k < 9; k++)
				if (sudoku->info[i][j][k] == MAYBE) break;
			if (set_cell(sudoku, i, j, k + 1)) return 1;
			flag = -1;
			/* {printf("Counter >= 8 !\n"); exit(1);} */ 
		}
	return flag;
}
int find_rows(struct sudoku_info *sudoku)
{
	int i, j, k, counter, flag = 0;
	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
		{
			counter = 0;
			for (k = 0; k < 9; k++)
			{
				if (sudoku->info[k][j][i] == YES) {counter = -1; break;}
				if (sudoku->info[k][j][i] == NO) counter++;
			}
			if (counter < 8) continue;
			if (counter > 8) return 1;
			for (k = 0; k < 9; k++)
				if (sudoku->info[k][j][i] == MAYBE) break;
			if (k == 9)
				{printf("Internal error (find_rows)\n"); exit(1);} /* for testing */
			if (set_cell(sudoku, k, j, i + 1))
				{/*printf("Internal error\n"); test();*/ return 1;}
			flag = -1;
		}
	return flag;
}
int find_columns(struct sudoku_info *sudoku)
{
	int i, j, k, counter, flag = 0;
	for (i = 0; i < 9; i++)
		for (j = 0; j < 9; j++)
		{
			counter = 0;
			for (k = 0; k < 9; k++)
			{
				if (sudoku->info[j][k][i] == YES) {counter = -1; break;}
				if (sudoku->info[j][k][i] == NO) counter++;
			}
			if (counter < 8) continue;
			if (counter > 8) return 1;
			for (k = 0; k < 9; k++)
				if (sudoku->info[j][k][i] == MAYBE) break;
			if (k > 8)
				{printf("Internal error (find_columns)\n"); exit(1);} /* for testing */
			if (set_cell(sudoku, j, k, i + 1)) return 1;
			flag = -1;
		}
	return flag;
}
int find_grids(struct sudoku_info *sudoku)
{
	int i, j, k, l, m, counter, flag = 0;
	for (i = 0; i < 9; i++)
		for (j = 0; j < 3; j++)
			for (k = 0; k < 3; k++)
			{
				counter = 0;
				for (l = j * 3; l < (j + 1) * 3; l++)
				{
					for (m = k * 3; m < (k + 1) * 3; m++)
					{
						if (sudoku->info[l][m][i] == YES) {counter = -1; break;}
						if (sudoku->info[l][m][i] == NO) counter++;
					}
					if (counter == -1) break;
				}
				if (counter < 8) continue;
				if (counter > 8) return 1;
				for (l = j * 3; l < (j + 1) * 3; l++)
				{
					for (m = k * 3; m < (k + 1) * 3; m++)
						if (sudoku->info[l][m][i] == MAYBE) break;
					if ((m < (k + 1) * 3) && sudoku->info[l][m][i] == MAYBE) break;
				}
				if (m == (k + 1) * 3)
					{printf("Internal error (find_grids)\n"); exit(1);} /* for testing */
			if (set_cell(sudoku, l, m, i + 1)) return 1;
			flag = -1;
		}
	return flag;
}
void display_grid(struct sudoku_info *sudoku)
{
	int i, j;
	/* printf("---------"); */
	printf("\n");
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			printf("%d", sudoku->grid[i][j]);
			if (j % 3 == 2) printf("  ");
		}
		printf("\n");
		if (i % 3 == 2) printf("\n");
	}
	/* printf("---------\n"); */
}
